package zcw.com.lib_leet_code;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by 朱城委 on 2021/7/26.<br><br>
 *
 * 括号生成
 */
public class Topic22 {

    public static void main(String[] args) {
        Topic22 instance = new Topic22();

        System.out.println(instance.generateParenthesis(1));
        System.out.println(instance.generateParenthesis(2));
        System.out.println(instance.generateParenthesis(3));
        System.out.println(instance.generateParenthesis(4));
    }

    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();

        helper(n, n, "", result);
        return result;
    }

    private void helper(int left, int right, String path, List<String> result) {
        if(left < 0 || right < 0 || left > right) {
            return ;
        }

        if(left == 0 && right == 0) {
            result.add(path);
            return ;
        }

        helper(left - 1, right, path + "(", result);
        helper(left, right - 1, path + ")", result);
    }
}
